package class04

import "math"

/*
	给定一个矩阵，返回子矩阵最大的累加和

	滚动素组 + 子数组的最大累加和

	思路：
		暴力情况下，选择一个随机矩形 N^2*N^2，计算 N^2 总共复杂度 N^6
		采用滚动数组每次计算行：0-0 0-1 0-3 ... 0-n
			                 1-1 1-2 1-3 1-4 .. 1-n
							...
		每到一个行就算一次 子数组的最大累加和

	优化：
		使用 更小的行或者列

*/
func matrixMaxSum(matrix [][]int) int {
	var ScrollingArr []int
	ans := math.MinInt
	for i:=0; i<len(matrix); i++ {
		ScrollingArr = make([]int, len(matrix[0]))
		for j:=i; j<len(matrix); j++ {
			cur := 0
			for z:=0; z<len(matrix[0]); z++ {
				ScrollingArr[z] += matrix[j][z]
				cur += ScrollingArr[z]
				ans = max(ans, cur)
				if cur < 0 {
					cur = 0
				}
			}
		}
	}
	return ans
}
